package oct2013.linkednode;

import java.util.HashMap;

public class CloneGraph {
	HashMap<UndirectedGraphNode, UndirectedGraphNode> map;

	public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
		if (node == null)
			return null;
		map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
		return dfs(node);
	}

	UndirectedGraphNode dfs(UndirectedGraphNode node) {
		UndirectedGraphNode newNode = map.get(node);
		if (newNode != null)
			return newNode;
		newNode = new UndirectedGraphNode(node.label);
		map.put(node, newNode);
		for (UndirectedGraphNode next : node.neighbors) {
			newNode.neighbors.add(dfs(next));
		}
		return newNode;
	}
}
